package leetcode;

public class ClimbingStairs70 {

	public static void main(String[] args) {
		System.out.println(climbStairs(44));
	}

	public static int climbStairs(int n) {
//		if(n == 1)
//            return 1;
//		if(n == 2)
//			return 2;
//		int first = 1, second = 2;
//		for(int i = 3; i < n; i++) {
//			int temp = first + second;
//			first = second;
//			second = temp;
//		}
//		return first + second;
		
		if(n == 1)
			return 1;
		if(n == 2)
			return 2;
		int[] history = new int[n];
		history[0] = 1;
		history[1] = 2;
		for(int i = 2; i < n; i++) {
			history[i] = history[i - 1] + history[i - 2];
		}
		return history[n - 1];
	}

}
